% !TEX root = pagerank.tex

\section{Introduction}\label{sec:intro}

In the last decade, PageRank has emerged as a very powerful measure of relative importance of nodes in a network. The term PageRank was first introduced in \cite{anatomy+page98,page99} where it was used to rank the importance of webpages on the Web. Since then, PageRank has found a wide range of applications in a variety of domains within computer science such as distributed networks, data mining, Web algorithms, and distributed computing \cite{pr-survey+05,Bianchini05,cook04,LangvilleM03}. Since PageRank vector or PageRanks is essentially the steady state distribution or the top eigenvector of the Laplacian corresponding to a slightly modified random walk process, it is an easily defined quantity. However, the power and applicability of PageRank arises from its basic intuition of being a way to naturally identify ``important'' nodes, or in certain cases, similarity between nodes. 

While there has been recent work on performing random walks efficiently in distributed networks \cite{ppr-bahmani2010,atish+pods08}, surprisingly, little  provable results are known towards efficient distributed computation of PageRanks. This is perhaps because the traditional method of computing PageRanks is to apply iterative methods i.e., do matrix-vector multiplications till (near)-convergence. Since such techniques may not adapt well in certain settings, when dealing with a global network with only local views (as is common in distributed networks such as Peer-to-Peer (P2P) networks), and particularly, very large networks, it becomes crucial to design far more efficient  techniques. Therefore, PageRank computation using Monte Carlo methods is more appropriate in a distributed model where only messages of limited size are permitted to be sent over each edge in each round.

To elaborate, a naive way to compute PageRank of nodes  in a distributed network is simply scaling iterative PageRank algorithms to
distributed environment. But this is firstly not trivial, and secondly expensive even if doable. As each iteration step needs computation results of previous steps, there needs to be continuous synchronization and several messages may need to be exchanged.  Further, the convergence time may be large. It is important to design efficient and localized distributed algorithms as communication overhead is more important than CPU and memory usage in distributed page ranking. We take all these concerns into consideration and design highly efficient fully decentralized algorithms for computing the PageRank vector in  distributed networks. \\

\noindent{\bf Our Contributions.}
In this paper, to the best of our knowledge, we present the first provably efficient fully decentralized algorithms for estimating PageRanks under a variety of settings. Our algorithms are scalable, since each node  sends only $\polylog n$ bits per round. 
%Thus our algorithms 
%work in the well-studied {\sc CONGEST} distributed computing model \cite{peleg}, where there is
%a restriction on the number of bits (typically,  $\polylog n$) that can be sent per edge per round. 
Specifically, our contributions are as follows:
\begin{itemize}
\renewcommand{\labelitemi}{$\bullet$}
\item We present an algorithm, {\sc Basic-PageRank-Algorithm} (cf. Algorithm \ref{alg:simple-pagerank-walk}), that computes  PageRanks accurately in $O(\frac{\log n}{\eps})$ rounds with high probability\footnote{Throughout, ``with high probability (w.h.p.)" means with probability at least $1 - 1/n^{c}$, where $n$ is the number of nodes in the network and $c > 1$ is  a suitably chosen constant.}, where $n$ is the number of nodes in the network and $\eps$ is the random reset probability in the PageRank random walk \cite{mcm-avrachenkov,ppr-bahmani2010,atish+pods08}. Our algorithm works for any arbitrary network (directed as well as undirected).\\

\item We present an improved algorithm, called as {\sc Improved-PageRank-Algorithm} (cf. Algorithm \ref{alg:pr-walk-undirected}), that computes  PageRanks accurately in {\em undirected graphs} and terminates with high probability in $O(\frac{\sqrt{\log n}}{\eps})$ rounds. We note that though PageRank is usually applied for directed graphs (e.g., for the World
Wide Web), it is sometimes also applied in connection with undirected 
graphs as well \cite{fanchung06,undirected12,IvanG11,PhysRev08,Wang07} and is non-trivial to compute (cf. Section \ref{sec:pagerank-def}). In particular, it can be applied for distributed networks when modeled as undirected graphs (as is typically the case, e.g., in P2P network models).  
\end{itemize}

\noindent We note that the {\sc Improved-PageRank-Algorithm} requires only $O(\log^3 n)$ bits to be sent per round per edge, and  the {\sc Basic-PageRank-Algorithm} requires only $O(\log n)$ bits per round per edge.
% and works in the CONGEST model. 

%\item We present an improved algorithm for directed graphs (which is a modified version of the {\sc Improved-PageRank-Algorithm}) that computes \pr accurately and  terminates with high probability in $O(\sqrt{\frac{\log n}{\eps}})$ rounds, but it  requires a polynomial number of bits to be processed and sent per node in a round. Assuming  $\eps$ is a constant (which is typically the case), this algorithm as well as the  {\sc Improved-PageRank-Algorithm} yields a sub-logarithmic (in $n$) running time. Thus, in many networks, this running time can be substantially smaller  than even the network diameter e.g., in constant-degree networks, the diameter is $\Omega(\log n)$.
 
%\end{itemize}

%Anisur: Removing the Overview 

%\noindent{\bf Overview.} The rest of the paper is organized as follows. ADD THE PAPER SECTION ORGANIZATION HERE

\endinput